package com.c2b.algorithm.leetcode.jzoffer;

import java.util.Stack;

/**
 * <a href="">包含min函数的栈</a>
 * <p>
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
 * </p>
 *
 * @author c2b
 * @since 2023/3/7 18:18
 */
public class JzOffer0030StackContainingMinFunction {
    /**
     * 正常栈
     */
    Stack<Integer> stack = new Stack<>();
    /**
     * 最小值栈
     */
    Stack<Integer> minStack = new Stack<>();

    /**
     * 维持两个栈中元素的数量相等。
     * <p>
     * 正常栈中每次都需要压入元素<br>
     * 1.如果最小值栈中无元素，直接在最小值栈中压入当前元素<br>
     * 2.如果最小值栈中有元素，需要判断最小值栈栈顶的元素和元素元素值的大小：<br>
     *      a.如果最小值栈栈顶元素小于等于压入元素，再次压入栈顶元素即可<br>
     *      b.如果最小值栈栈顶元素大于压入元素，将压入的新元素压入最小值栈栈顶元素即可<br>
     * </p>
     *
     * @param node 压入的元素值
     */
    public void push(int node) {
        stack.push(node);
        if (minStack.empty() || minStack.peek() <= node) {
            minStack.push(node);
        } else {
            minStack.push(node);
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        //  ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
        JzOffer0030StackContainingMinFunction jzOffer0030StackContainingMinFunction = new JzOffer0030StackContainingMinFunction();
        jzOffer0030StackContainingMinFunction.push(2);
        jzOffer0030StackContainingMinFunction.push(3);
        jzOffer0030StackContainingMinFunction.push(6);
        jzOffer0030StackContainingMinFunction.push(2);
        jzOffer0030StackContainingMinFunction.push(4);
        jzOffer0030StackContainingMinFunction.push(5);
        jzOffer0030StackContainingMinFunction.pop();
        jzOffer0030StackContainingMinFunction.pop();
        jzOffer0030StackContainingMinFunction.pop();
        System.out.println(jzOffer0030StackContainingMinFunction.min());
    }
}
